package com.celan.year2023.month11.day04;

import java.util.HashSet;

/**
 * @author Celan
 * @description TODO
 */
public class Solution {
    // 最高位为 30
    private final static int HIGH_BIT = 30;

    public int findMaximumXOR(int[] nums) {
        int x = 0;
        // 从右到左枚举每一位
        for (int i = HIGH_BIT; i >= 0; i--) {
            HashSet<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num >> i);
            }
            int xNext = x * 2 + 1;
            boolean found = false;
            for (int num : nums) {
                if (set.contains(xNext ^ (num >> i))) {
                    found = true;
                    break;
                }
            }
            if (found) {
                x = xNext;
            } else {
                x = xNext - 1;
            }
        }
        return x;
    }
}
